#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串vector
     */
    string path;
    vector<string> ret;
    vector<bool> isused;
    void dfs(string& str,int index)
    {
        if(index>=str.size())
        {
            ret.push_back(path);
            return;
        }
        for(int i = 0;i<str.size();i++)
        {
            if(!isused[i])
            {
                if(i>=1&&str[i-1] == str[i]&&isused[i-1])
                {
                    continue;//如果i元素和i-1元素是相同的，并且i-1元素被使用过了，那么当前元素
                    //就没必要去使用了
                }
                path.push_back(str[i]);
                isused[i] = true;
                dfs(str,index+1);
                path.pop_back();
                isused[i] = false;
            }
        }
    }
    vector<string> Permutation(string str) {
        sort(str.begin(),str.end());//为去重做准备
        isused.resize(str.size(),false);
        dfs(str,0);
        return ret;    
    }
};